/*
ID: icerupt1
PROG: inflate
LANG: C++11
*/

/* solution
 *
 *
 *
*/
#include <fstream>
#include <iostream>

std::ifstream fin {"inflate.in" };
std::ofstream fout{"inflate.out"};

int const maxm = 10001;
int f[maxm];
int n, m;

int main()
{
	fin >> m >> n;
	for (int i = 0, x, y; i < n; i++) {
		fin >> x >> y;
		for (int j = 0; j <= m; j++)
			if (j >= y) f[j] = std::max(f[j], f[j-y] + x);
	}
	std::cout << f[m] << '\n';
	fout << f[m] << '\n';
}
